import collections
from typing import List


class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        """
        边的形式是[u, v] u<v
        如果是保持一颗树的形状的话，那么通过并查集查找会发现 所有节点的最上头的父节点都是最小的那个节点
        由此可以验证去掉一条边后还是否保持了树的形状
        """
        father = collections.defaultdict(set)
        node_num = set()
        for fatherID, nodeID in edges:
            father[nodeID].add(fatherID)
            node_num.add(fatherID)
            node_num.add(nodeID)

        node_num = len(node_num)

        print(father)
        # 不做路径优化

        def validWithoutOneEdge(edge):

            fathers = [False] * node_num  # 父节点为1 则为True
            fathers[1 - 1] = True

            fatherID, nodeID = edge
            father[nodeID].remove(fatherID)
            print(father)

            def getF(nodeID):
                node_fathers = []

                def getFather(nodeID):
                    if nodeID == 1:
                        node_fathers.append(1)
                    elif nodeID not in father:
                        node_fathers.append(nodeID)
                    elif len(father[nodeID]) == 0:
                        node_fathers.append(nodeID)
                    else:
                        for fID in father[nodeID]:
                            getFather(fID)

                getFather(nodeID)  # 老毛病了 定义了函数 不调用
                return node_fathers

            for i in range(2, node_num+1):
                node_fathers = getF(i)
                print(i, node_fathers)
                if 1 in node_fathers:
                    fathers[i - 1] = True

            father[nodeID].add(fatherID)
            if False in fathers:
                return False
            return True

        for edge in edges[::-1]:
            # print(edge)
            if validWithoutOneEdge(edge) == True:
                return edge

edges = [[1,3],[3,4],[1,5],[3,5],[2,3]]
print(Solution().findRedundantConnection(edges))